package com.leetcode.algorithm.y22.m08.w1;

/**
 * 200. 岛屿数量
 * 
 * https://leetcode.cn/problems/number-of-islands/
 * 
 * @author jie.deng
 *
 */
class Question0200Solution05 {

	public int numIslands(char[][] grid) {
		// 并查集
		int zeroCnt = 0;
		int rows = grid.length;
		int cols = grid[0].length;
		UnionFind uf = new UnionFind(rows * cols);
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (grid[row][col] == '1') {
					int curIdx = row * cols + col;
					for (int[] dir : new int[][] { { 0, -1 }, { -1, 0 } }) {
						// 左和上
						int r = row + dir[0];
						int c = col + dir[1];
						if (r >= 0 && r < rows && c >= 0 && c < cols) {
							if (grid[r][c] == '1') {
								int idx = r * cols + c;
								uf.union(curIdx, idx);
							}
						}
					}
				} else {
					zeroCnt++;
				}
			}
		}
		return uf.count - zeroCnt;
	}

	class UnionFind {
		// 实际存储的是parent
		int roots[];
		int count;

		public UnionFind(int size) {
			roots = new int[size];
			for (int i = 0; i < size; i++) {
				roots[i] = i;
			}
			count = size;
		}

		private int findRoot(int x) {
			if (x == roots[x]) {
				return x;
			}
			// 路径压缩
			return x = findRoot(roots[x]);
		}

		public void union(int x, int y) {
			int rootX = findRoot(x);
			int rootY = findRoot(y);
			if (rootX != rootY) {
				roots[rootY] = rootX;
				count--;
			}
		};

	}

}